#Create all unique permutations from a list of lists by picking one element from every list
#Example:
#UP([[1,2],[3,4,5]])= [[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]

def UP2(l1,l2):
    """"Return UP of two lists"""
    ltemp =[]
    for x1 in l1:
        for x2 in l2:
            ltemp.append([x1,x2])

    return ltemp

def UP(li):
    """Return UP of a general list"""
    lcurrent = li[0]
    depth = 0
    for xl in li[1:]:
        lcurrenttemp = list()
        lcurrenttemp = UP2(lcurrent,xl)

        if depth > 0:
            lcurrent = list()
            for item in lcurrenttemp:
                item0 = list(item[0])
                item0.append(item[1])
                lcurrent.append(item0)                
        else:
            lcurrent = lcurrenttemp[:]            
        depth += 1
    return lcurrent

if __name__ == '__main__':
    print UP2([1,2],[3,4,5])
    #Result
    #[[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5]]

    print UP([[1,2],[3,4,5],[5,6,7],[8,9]])
    #Result
    #[[1, 3, 5, 8], [1, 3, 5, 9], [1, 3, 6, 8], [1, 3, 6, 9], [1, 3, 7, 8], [1, 3, 7, 9], [1, 4, 5, 8], [1, 4, 5, 9], [1, 4, 6, 8], [1, 4, 6, 9], [1, 4, 7, 8], [1, 4, 7, 9], [1, 5, 5, 8], [1, 5, 5, 9], [1, 5, 6, 8], [1, 5, 6, 9], [1, 5, 7, 8], [1, 5, 7, 9], [2, 3, 5, 8], [2, 3, 5, 9], [2, 3, 6, 8], [2, 3, 6, 9], [2, 3, 7, 8], [2, 3, 7, 9], [2, 4, 5, 8], [2, 4, 5, 9], [2, 4, 6, 8], [2, 4, 6, 9], [2, 4, 7, 8], [2, 4, 7, 9], [2, 5, 5, 8], [2, 5, 5, 9], [2, 5, 6, 8], [2, 5, 6, 9], [2, 5, 7, 8], [2, 5, 7, 9]]
